<!-- HTML header for doxygen 1.8.13-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.14"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow Handbook</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link rel="icon" type="image/x-icon" href="favicon.ico" />
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
  $(document).ready(initResizable);
/* @license-end */</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname"><a href="https://taskflow.github.io/">Taskflow</a>
   &#160;<span id="projectnumber">3.0.0-Master-Branch</span>
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.14 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
var searchBox = new SearchBox("searchBox", "search",false,'Search');
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
/* @license-end */</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(document).ready(function(){initNavTree('flipcoins.html','');});
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Flip Coins </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>We study dynamic control flow of non-determinism using conditional tasking. Non-deterministic control flow is a fundamental building block in many optimization and simulation algorithms that rely on stochastic convergence rules or probabilistic pruning.</p>
<h1><a class="anchor" id="FlipCoinsProblemFormulation"></a>
Problem Formulation</h1>
<p>We have a fair binary coin and want to simulate its tosses. We flip the coin for five times. Apparently, the probability for the result to be all heads is 1/32. It is equivalently to say the expected number we need to toss for obtaining five heads is 32.</p>
<div class="image">
<object type="image/svg+xml" data="flipcoins_1.svg" width="80%">flipcoins_1.svg</object>
</div>
<h1><a class="anchor" id="FlipCoinsProbabilistic"></a>
Probabilistic Conditions</h1>
<p>We use condition tasks to simulate the five coin tosses. We create five condition tasks each returning a random binary number. If the return is zero (head toss), the execution moves to the next condition task; or it (tail toss) goes back to the first condition task to start over the simulation.</p>
<div class="fragment"><div class="line"><a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"><a class="code" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div><div class="line"></div><div class="line"><span class="keywordtype">size_t</span> rounds = 10000;</div><div class="line"><span class="keywordtype">size_t</span> tosses = 0; </div><div class="line"><span class="keywordtype">size_t</span> total_tosses = 0; </div><div class="line"><span class="keywordtype">double</span> average_tosses = 0.0; </div><div class="line"></div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> A = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ tosses = 0; } ).name(<span class="stringliteral">&quot;init&quot;</span>); </div><div class="line"></div><div class="line"><span class="comment">// start over the flip again</span></div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> B = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ ++tosses; <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; } ).name(<span class="stringliteral">&quot;flip-coin-1&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> C = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; } ).name(<span class="stringliteral">&quot;flip-coin-2&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> D = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; } ).name(<span class="stringliteral">&quot;flip-coin-3&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> E = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; } ).name(<span class="stringliteral">&quot;flip-coin-4&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> F = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; } ).name(<span class="stringliteral">&quot;flip-coin-5&quot;</span>);</div><div class="line"></div><div class="line"><span class="comment">// reach the target; record the number of tosses </span></div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> G = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ total_tosses += tosses; } ).name(<span class="stringliteral">&quot;stop&quot;</span>);</div><div class="line"></div><div class="line">A.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B);</div><div class="line"></div><div class="line"><span class="comment">// five probabilistic conditions</span></div><div class="line">B.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(C, B);</div><div class="line">C.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(D, B);</div><div class="line">D.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(E, B);</div><div class="line">E.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(F, B);</div><div class="line">F.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(G, B);</div><div class="line"></div><div class="line"><span class="comment">// repeat the flip-coin simulation by rounds times</span></div><div class="line">executor.<a class="code" href="classtf_1_1Executor.html#adca6cd0ce1bd7e6fa2ed2a55c9ae15e6">run_n</a>(taskflow, rounds).wait();</div><div class="line"></div><div class="line"><span class="comment">// calculate the expected number of tosses</span></div><div class="line">average_tosses = total_tosses / (double)rounds;</div><div class="line"></div><div class="line">assert(std::fabs(average_tosses-32.0)&lt;1.0);</div></div><!-- fragment --><p>Running the taskflow by a fair number of times, the average tosses we have is close to 32. The taskflow diagram is depicted below.</p>
<div class="image">
<object type="image/svg+xml" data="flipcoins_2.svg" width="100%">flipcoins_2.svg</object>
</div>
<p>Although the execution of this taskflow is non-deterministic, its control flow can expand to a tree of tasks based on our scheduling rule for conditional tasking (see <a class="el" href="chapter4.html">C4: Conditional Tasking</a>). Each path from the root to a leaf represents a result of five heads, and none of them can overlap at the same time (no task race). You must follow the same rule when creating a probabilistic framework using conditional tasking.</p>
<h1><a class="anchor" id="FlipCoinsTernaryCoins"></a>
Ternary Coins</h1>
<p>We can extend the binary coin example to a ternary case. Each condition task has one successor going back to the beginning and two successors moving to the next task. The expected number of tosses to reach five identical results is 3*3*3*3*3 = 243.</p>
<div class="fragment"><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> A = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ tosses = 0; } ).name(<span class="stringliteral">&quot;init&quot;</span>); </div><div class="line"></div><div class="line"><span class="comment">// start over the flip again</span></div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> B = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ ++tosses; <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%3; } ).name(<span class="stringliteral">&quot;flip-coin-1&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> C = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%3; } ).name(<span class="stringliteral">&quot;flip-coin-2&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> D = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%3; } ).name(<span class="stringliteral">&quot;flip-coin-3&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> E = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%3; } ).name(<span class="stringliteral">&quot;flip-coin-4&quot;</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> F = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/Users/twhuang/PhD/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%3; } ).name(<span class="stringliteral">&quot;flip-coin-5&quot;</span>);</div><div class="line"></div><div class="line"><span class="comment">// reach the target; record the number of tosses </span></div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> G = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a60d7a666cab71ecfa3010b2efb0d6b57">emplace</a>( [&amp;](){ total_tosses += tosses; } ).name(<span class="stringliteral">&quot;stop&quot;</span>);</div><div class="line"></div><div class="line">A.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B);</div><div class="line"></div><div class="line"><span class="comment">// five probabilistic conditions</span></div><div class="line">B.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(C, B, B);</div><div class="line">C.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(D, B, B);</div><div class="line">D.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(E, B, B);</div><div class="line">E.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(F, B, B);</div><div class="line">F.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(G, B, B);</div><div class="line"></div><div class="line"><span class="comment">// repeat the flip-coin simulation by rounds times</span></div><div class="line">executor.<a class="code" href="classtf_1_1Executor.html#adca6cd0ce1bd7e6fa2ed2a55c9ae15e6">run_n</a>(taskflow, rounds).wait();</div><div class="line"></div><div class="line"><span class="comment">// calculate the expected number of tosses</span></div><div class="line">average_tosses = total_tosses / (double)rounds;</div><div class="line"></div><div class="line">assert(std::fabs(average_tosses-243.0)&lt;1.0);</div></div><!-- fragment --><div class="image">
<object type="image/svg+xml" data="flipcoins_3.svg" width="100%">flipcoins_3.svg</object>
</div>
<p>Similarly, we can extend the probabilistic condition to any degree. </p>
</div></div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="navelem"><a class="el" href="Examples.html">Learning from Examples</a></li>
    <li class="footer">Generated by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.14 </li>
  </ul>
</div>
</body>
</html>
